package srcInterviewPrep;

public final class TortoiseHareCycleDetector
{
    public static MulLambdaPair FindCycle(TortoiseHareNode a)
    {
        // null check for a

        TortoiseHareNode t = a;
        TortoiseHareNode h = a;

        while (h != null && h.next != null)
        {
            t = t.next;
            h = h.next.next;
            
            if (t == h)
            {
                break;
            }
        }
        
        if (h == null || h.next == null)
        {
            throw new RuntimeException("Linked list does not have a cycle");
        }        

        h = a;

        while (t != h)
        {
            h = h.next;
            t = t.next;
        }

        TortoiseHareNode mu = h;
        int lambda = 1;
        h = h.next;

        while (t != h)
        {
            h = h.next; 
            ++lambda;
        }

        return new MulLambdaPair(mu, lambda);
    }    

    public static final class MulLambdaPair
    {
        TortoiseHareNode mu;
        int lambda;

        public MulLambdaPair(TortoiseHareNode mu, int lambda)
        {
            this.mu = mu;
            this.lambda = lambda;
        }
    }

    public static final class TortoiseHareNode
    {
        int data;
        TortoiseHareNode next;

        public TortoiseHareNode(int data)
        {
            this.data = data;
        }
    }

}
